package arithmetic;

import java.util.Scanner;

/**
 * @program: javaLearn
 * @description: 最优二叉搜索树
 * @author: renhai
 * @Date ：2022/5/5 15:12
 **/
public class OptimalBinarySearchTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();//树的结点数目
        double arr[] = new double[num * 2 + 1];//用来存取概率分布（a0,b1,a1,b2,a2,...,bn,an）
        for (int i = 0; i < num * 2 + 1; i++) {
            arr[i] = scanner.nextDouble();
        }

        int s[][] = new int[num + 2][num + 2];//用来记录i到j取最小值时的做根的结点是多少。
        double w[][] = new double[num + 2][num + 2];//用来记录i到j的所有概率之和
        double m[][] = new double[num + 2][num + 2];//用来记录i到j取的最小值的值

        for (int i = 0; i <= num; i++) {//初始化
            w[i + 1][i] = arr[i * 2];
            m[i + 1][i] = 0;
        }


        for (int i = 1; i <= num; i++) {
            //考虑i个结点的各个情况，从考虑一个结点到考虑num个结点
            for (int k = 1; k <= num - i + 1; k++) {
                //取从k到j的结点，总共有num-i+1种取法
                int j = k + i - 1;//截止的地方
                m[k][j] = 2147483647;//附一个最大的int值,便于后面的比较
                w[k][j] = w[k][j - 1] + arr[j * 2] + arr[j * 2 - 1];
                //将i到j的所有概率之和赋值
                for (int f = k; f <= j; f++) {
                    //从k到j这段结点中，找出f的值当做树根使得这段结点组成的树为最优二叉搜索树
                    double x = m[k][f - 1] + m[f + 1][j] + w[k][j];
                    if (x < m[k][j]) {
                        m[k][j] = x;
                        s[k][j] = f;
                    }
                }
            }
        }
        System.out.println("先序遍历");
        print(s, 1, num);
        scanner.close();
    }

    public static void print(int s[][], int i, int j) {
        if (i > j) {
            return;
        } else {
            System.out.print(s[i][j] + " ");
            print(s, i, s[i][j] - 1);
            print(s, s[i][j] + 1, j);
        }
    }
}



